// https://www.lintcode.com/problem/previous-permutation/

public class Solution {
    /*
     * @param nums: A list of integers
     * @return: A list of integers that's previous permuation
     */
    public List<Integer> previousPermuation(List<Integer> nums) {
        // write your code here
        // 以162543为例，上一个应该是163534。步骤如下：
        // 1. 找到最后一个num[i] >= num[i - 1]的点
        // 2. 如果i = 0，逆序返回即可。
        // 3. 从num[i + 1]到num[-1]找到小于于num[i - 1]的最大数，并与num[i - 1]交换位置。
        // 4. 对num[i + 1]到num[-1]逆序排序
        int nlen = nums.size();
        int i = nlen - 1;
        while (i > 0) {
            if (nums.get(i) >= nums.get(i - 1)) {
                --i;
            } else {
                break;
            }
        }
        if (i == 0) {
            reverse(nums, 0, nlen - 1);
            return nums;
        }
        int mval = nums.get(i);
        int mpos = i;
        for (int j = i; j < nlen; ++j) {
            if ((nums.get(j) < nums.get(i - 1)) && (nums.get(j) > mval)) {
                mval = nums.get(j);
                mpos = j;
            }
        }
        swap(nums, i - 1, mpos);
        List<Integer> plist = new ArrayList<>();
        for (int j = nlen - 1; j >= i; --j) {
            plist.add(nums.remove(nums.size() - 1));
        }
        Collections.sort(plist, new Comparator<Integer>() {
            @Override
            public int compare(Integer v1, Integer v2) {
                return v2 - v1;
            }
        });
        for (Integer v : plist) {
            nums.add(v);
        }
        return nums;
    }
    
    private void reverse(List<Integer> nums, int i, int j) {
        while (i < j) {
            swap(nums, i, j);
            ++i;
            --j;
        }
    }
    
    private void swap(List<Integer> nums, int i, int j) {
        int t = nums.get(i);
        nums.set(i, nums.get(j));
        nums.set(j, t);
    }
}